// https://www.lintcode.com/problem/makeequilateraltriangle/

public class Solution {
    /**
     * @param lengths: the lengths of sticks at the beginning.
     * @return: return the minimum number of cuts.
     */
    public int makeEquilateralTriangle(int[] lengths) {
        // write your code here.
        int ret = 2; // 最多2刀
        Set<Integer> set = new HashSet<>();
        for (int l : lengths) {
            set.add(l);
        }
        Arrays.sort(lengths);
        for (int i = 0; i < (lengths.length - 2); ++i) {
            int i1 = lengths[i];
            int i2 = lengths[i + 1];
            int i3 = lengths[i + 2];
            if ((i1 == i2) && (i2 == i3)) {
                return 0;
            } else if ((i1 == i2) || (i2 == i3) || (set.contains(i1 * 2))) {
                ret = 1;
            }
        }
        return ret;
    }
}